package cn.edu.xjtu.carlWay.tree.bottomLeftVal;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 513. 找树左下角的值
 * 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
 * <p>
 * 假设二叉树中至少有一个节点。
 * <p>
 * https://leetcode-cn.com/problems/find-bottom-left-tree-value/
 */
public class Solution {
    /**
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        int leftVal = 0;
        while (!deque.isEmpty()) {
            leftVal = deque.peekFirst().val;
            int size = deque.size();
            while (size > 0) {
                TreeNode node = deque.removeFirst();
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
                size--;
            }
        }
        return leftVal;
    }
}
